package com.kevin.Code.LinkNode;

/**
 * @author Vinlee Xiao
 * @Classname ReorderList
 * @Description Leetcode 143. 重排链表 中等难度 高频题
 * @Date 2021/11/9 20:48
 * @Version 1.0
 */
public class ReorderList {

    /**
     * 自己的思路
     * 双指针思路
     *
     * @param head
     */
    public void reorderList(ListNode head) {

        //如果为1个结点或者两个结点则直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }

        ListNode preNode = new ListNode(-1);
        preNode.next = head;
        ListNode slow = head;
        ListNode fast = head;
        ListNode move = head;
        //快慢指针找到链表的中间结点
        //快指针找到中点
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        //slow指针指向的点中点
        ListNode secondNode = slow.next;
        //将slow结点置为空
        slow.next = null;
        ListNode secondDummy = new ListNode(-1);
        ListNode secondPre = secondDummy;
        //翻转当前链表
        ListNode secondHead = new ListNode(0);

        while (secondNode != null) {
            ListNode node = secondNode;
//            System.out.print(node.val+" ");
            if (secondNode.next == null) {
                secondHead = secondNode;
            }
            secondNode = secondNode.next;
            node.next = secondPre;
            secondPre = node;

        }


        while (move != null && secondHead != secondDummy) {
            ListNode aNode = move;
            ListNode bNode = secondHead;
            move = move.next;
            secondHead = secondHead.next;

            preNode.next = aNode;
            aNode.next = bNode;
            preNode = bNode;

        }
//        System.out.println(move.val);
        preNode.next = move != null ? move : null;
    }

    public static void main(String[] args) {
        ReorderList reorderList = new ReorderList();
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
//        ListNode head5 = new ListNode(5);
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
//        head4.next = head5;
        reorderList.reorderList(head1);

        while (head1 != null) {
            System.out.println(head1.val);
            head1 = head1.next;
        }
    }
}
